In a network where a plurality of terminals (including a transmission terminal and a reception terminal) and relay devices are connected to each other, “congestion” can occur when data is transmitted from the transmission terminal to the reception terminal via relay devices. This causes problems such as a transmission error (data loss) and a data reception delay.
In the data transmission, a relay device which relays between the transmission terminal and the reception terminal temporarily stores the data transmitted from the transmission terminal (or another relay device) connected to the relay device, into one of buffers that each correspond to a different forwarding destination (the reception terminal or another relay device). The relay device then transmits the stored data to a forwarding destination of the data. For example, congestion is such a state where, as a result of data that exceeds a buffer capacity being transmitted to the relay device, a buffer overflow occurs and a data loss or a time delay in transmitting to the forwarding destination ensues. Which is to say, congestion means that transmission packets concentrate and crowd in one place and consequently a data loss or a data transmission delay occurs.
The following compares an environment of an ad hoc network (often also called a multi-hop network or a mesh network) that does not require an access point and is composed only of a plurality of terminals (for example, personal computers, PDAs, mobile phones, and the like) which are connectable wirelessly (for example, by a wireless Local Area Network (LAN) or Ultra Wide Band (UWB)), with an environment of a network having only wired connections or a network having both wired and wireless connections. In the ad hoc network environment, all terminals and relay devices are connected wirelessly, so that transmission between a transmission terminal and a relay device, between relay devices, and between a relay device and a reception terminal tends to become unstable. Hence a data loss or a time delay due to congestion arises easily.
Congestion in the ad hoc network environment can be attributed to two types of imbalance in packet remaining amount between a plurality of buffers.
One type of imbalance is an inequality in packet remaining amount between buffers that correspond to different forwarding destinations in one relay device. This causes an imbalance in loss or delay between a plurality of traffic flows.
The other type of imbalance is an inequality in packet remaining amount between buffers of relay devices that are located on a same transmission path. This induces congestion in a relay device on the transmission path.
As a method of reducing an imbalance in buffer remaining amount in one relay device to suppress a delay or a loss between traffic flows, Non-patent Reference 1 discloses the following technique. In a network where a wireless network, such as a wireless LAN or a mobile phone network, and a wired network are connected to each other, scheduling control of changing a transmission priority in each service such as video distribution, voice communication, and data communication is performed according to a transmission error rate of a wireless link in a gateway which interconnects the wired network and the wireless network, in order to alleviate a degradation in Quality of Service (QoS) caused by a variation in transmission error rate on a transmission path.
Also, as a method of reducing an imbalance in buffer remaining amount between relay devices to suppress congestion in a relay device, the following technique is proposed. Each relay device performs, for each forwarding destination node or each communication flow to an ultimate destination, autonomous distributed control of resources according to a network crowding level in a wireless network, based on load states of the relay device itself and its neighbor relay device.
In detail, Patent Reference 1 discloses a wireless bridge that constitutes an autonomous distributed wireless communication network, to address the above problem. This wireless bridge includes: a load detection unit that detects a load of the wireless bridge itself; a high load node judgment unit that judges a node having a high forwarding load concentration in the network, by exchanging the detected load information with another wireless bridge; a forwarding destination determination unit that determines a forwarding destination node of a received packet; and a resource allocation control unit that controls resource allocation for each forwarding destination node based on a result of judgment by the high load node judgment unit. According to this structure, in the wireless network, resources are controlled in an autonomous distributed manner for each forwarding destination node or each communication flow to an ultimate destination, depending on a network crowding level.
This technique, however, urges each relay device to try to secure its own resources as much as possible (self-optimization). Therefore, contention arises when allocating resources among relay devices.
To allow a plurality of nodes, which operate in an autonomous distributed manner, to control resource allocation in cooperation with each other, Patent Reference 2 and Non-patent Reference 2 propose the following methods.
In the method of Patent Reference 2, in addition to self-optimization control, total optimization control is simultaneously executed on each of a plurality of cameras which are capable of adjusting a photographing area (resource shared by the plurality of cameras) by pan/tilt/zoom control. The self-optimization control causes each individual camera to photograph directly below itself so that no distortion occurs. The total optimization control causes the plurality of cameras to photograph an entire surveillance area without any blind spot. To enable the system as a whole to fully achieve the two purposes of photographing directly below each individual camera and photographing the entire surveillance area, optimization control is performed on allocation of the photographing areas of the plurality of cameras to the surveillance area. It should be noted here that, to make the mutually contradictory operations of the self-optimization control and the total optimization control coexist in each camera, a ratio of the two types of control has been determined in advance through trial and error when setting up the plurality of cameras, in consideration of a room size, a number of cameras, and camera performance.
In the method of Non-patent Reference 2, the following self-optimization control and total optimization control are performed to ease traffic jams of vehicles at a plurality of intersections. The self-optimization control adjusts switching timings of traffic lights at each intersection according to a traffic volume of each destination, to reduce the number of vehicles stopping at a red light at the intersection. The total optimization control adjusts switching timings of traffic lights at each intersection so that vehicles can drive through an adjacent intersection without stopping.
It is to be noted here that, to make the self-optimization control and the total optimization control coexist at each traffic light, a ratio of the two types of control has been determined in advance in consideration of a number and placement of intersections and a distance between intersections.
Furthermore, Non-patent Reference 3 proposes a method of selecting an access point (party to be communicated with) to which a terminal is to transmit data, in a wireless multi-hop network having a plurality of access points.
In the method of Non-patent Reference 3, in a multi-hop wireless LAN where a plurality of access points are wirelessly connected to each other, a terminal autonomously selects an access point based on a reception electric field intensity, a transmission error rate, and a number of terminals connected to each access point.
Patent Reference 1: Japanese Unexamined Patent Application Publication No. 2005-303828
Patent Reference 2: Japanese Patent No. 3903062
Non-patent Reference 1: Kakami, “Wireless Scheduling Method for Assured Service”, Technical Report of IEICE, CQ2000-11, Vol. 100, No. 93 (2000), pp. 65-70
Non-patent Reference 2: Sugi, “Autonomous Distributed Control of Traffic Signal Network by Reaction-Diffusion Equation on a Graph”, The Society of Instrument and Control Engineers, Vol. 39, No. 1, January 2003
Non-patent Reference 3: Ohyabu, “Proposal and Evaluation of an Access Point Selection Strategy in Multihop Wireless LAN”, Technical Report of IEICE, IN2005-207, pp. 299-304